/*
* 1.左偏树/左式堆
    左偏树作为可并堆的一种数据结构，其重点在于将两个堆合并，
    在维护堆的性质之外，每个节点x另外维护一个信息dist[x]表示x到最近的叶子节点的距离
    且dist[l]>=dist[r]，从而保证合并复杂度O(logn) <- 根节点的距离<=logn


* 2.op
    (1) 插入一个数 O(logn)
    (2) 求最小值 O(1)
    (3) 删除最小值 O(logn)
    (4) 合并两棵树 O(logn)
        merge(a, b) 合并子树a,b，并返回合并后的根节点

* 本题:
    ai'-=i, bi'-=i; 此时问题转为求非严格递增的序列
    整个构造序列分成两段，现在我们要考虑每一段数取相同值，使得整个序列各项之差的绝对值之和最小
    各取每一段的中位数作为这两段的值就能让这两段的差值最小
    前半段Su最优解为A，Sv最优解为B,整个序列最优解的和为A+B
    前半段取u的和为Su>=A, 后半段取v的和为Sv>=B,下限则为最优解A+B

    u>=v,即前半段>=后半段，整个序列不是最优解，此时一定存在一组最优解，使得b[m]<=u
    如果此时b[m]>u, 由于u是前半段的最优解，因为b[1]~b[m]都变成u，就满足b[m]<=u
    同理也存在一组最优解，b[m+1]<v, 后半段全部替换成v，就能满足b[m+1]>=v

    再将后面k-1段下压到第一段的位置，后面k−1段中至少有一半的数是<=u的

    按照以上思路用每一段的中位数来进行合并，最终得到一个非下降的序列
    维护每一段区间的中位数，而维护一段区间的中位数是可以用堆来维护的，
    这里要维护多个区间，也就是维护多个堆，因此需要用到左偏树来维护所有的堆
    只有前一段的中位数小于后一段的中位数时才需要维护
    每次合并的时候只需要将堆合并再取新的堆的最大值就是新的中位数

    得到中位数之后考虑向上向下 abs=abs(a-b)
    奇数个数中位数唯一，无论向上或者向下，abs至少+1(存在变化)
        如果不小于前一段解，则解有效
        否则向前合并，继续找中位数
    偶数个数中位数，在中间两个数之间浮动
        (1)前一段的解在这两个数之间，再向前取
           否则向上虽然不影响结果，但是存在向下浮动的空间，如果考虑向下，还需要再向前合并增加abs
        (2)前一段解小于这个区间，取中间两个数最小
        (3)前一段解大于这个区间，取中间两个数最小，再向前合并
*/ 

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define DEBUG
using ll=long long;
inline int read()
{
	int x=0;char c=getchar();
	while (c<'0'||c>'9') c=getchar();
	while (c>='0'&&c<='9') x=(x<<1)+(x<<3)+c-48,c=getchar();
	return x;
}
inline void write(ll x)
{
	if (x>=10) write(x/10);
	putchar(x%10+48);
}//快读快输
const int N=1e6+10;
struct Segment
{
    int end, root, size; //终点 根节点(中位数编号) 大小
}stk[N]; int top;
int n;
int fa[N], val[N], l[N], r[N], dist[N]; //左偏树
int res[N];

int merge(int x, int y) //将x和y所在的左偏树合并，并返回合并后的根节点
{
    if(!x||!y) return x+y;
    if(val[x] < val[y]) swap(x, y); //当前区间中位数<前一段中位数 保证 x > y，则x是合并后根节点
    r[x]=merge(r[x], y); //将x的右子树和y合并
    if(dist[l[x]]<dist[r[x]]) swap(l[x], r[x]); //保证左子树的距离>右子树的距离
    dist[x]=dist[r[x]]+1; //右子树发生改变，更新根节点的距离
    return x;
}

int pop(int x) //删除以x为根的左偏树的根节点，并返回删除后的根节点
{
    return merge(l[x],r[x]);
}

void solve()
{
    n=read();
    
    for(int i=1; i<=n; i++)
    {
        val[i]=read()-i;
    }

    top=0;

    for(int i=1; i<=n; i++)
    {
        auto cur=Segment({i, i, 1}); //初始化每个数就是一个区间
        while(top && val[cur.root]<val[stk[top].root]) //当前区间中位数<前一个区间的中位数->合并两个区间
        {
            cur.root=merge(cur.root, stk[top].root);
            //对于每个区间，为了保证堆顶是中位数，堆中应该存区间长度/2(向上取整)
            //(偶 偶) 或 (奇 偶) > 直接合并 中位数取头
            //(奇 奇) -> 前两个向上取整，合并取中位数后相较于直接取头会多一个，需要弹出
            if(cur.size%2 && stk[top].size%2) cur.root=pop(cur.root);
            cur.size+=stk[top].size; //合并前面段更新size
            top--;
        }
        stk[++top]=cur;
    }  

    for(int i=1, j=1; i<=top; i++)
        while(j<=stk[i].end) res[j++]=val[stk[i].root];
    ll sum=0;
    for(int i=1; i<=n; i++) sum+=abs(val[i]-res[i]);
    write(sum); puts("");
    for(int i=1; i<=n; i++) write(res[i]+i), putchar(' ');
    puts("");
}

signed main()
{
    #ifdef DEBUG
        freopen("./in.txt","r",stdin);
        freopen("./out.txt","w",stdout);
    #endif

    
    int T=1; //T=read();
    while(T--)
    {
        solve();
    }
    return 0;
}